package com.cdream.basic.algorithm.leetcode.linkedlist;

import java.util.*;

/**
 * @author cdream
 * @date 7/13/21
 */
public class Question218 {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        // 楼的边缘
        List<Integer> boundaries = new ArrayList<>();
        for (int[] building : buildings) {
            boundaries.add(building[0]);
            boundaries.add(building[1]);
        }

        Collections.sort(boundaries);
        // 结果集
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        int n = buildings.length, idx = 0;

        for (Integer boundary : boundaries) {
            // 左边缘小于关键点的都加进来
            while (idx < n && buildings[idx][0] <= boundary) {
                pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
                idx++;
            }
            // 如果最高点是右边缘，就给删掉
            while (!pq.isEmpty() && pq.peek()[0]<=boundary){
                pq.poll();
            }
            // 如果纵左边连续，则跳过
            int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
            if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
                ret.add(Arrays.asList(boundary, maxn));
            }
        }
        return ret;
    }

    public  static int binarySearch(int[] rec, int target) {
        int low = 0, high = rec.length - 1;
        if (rec[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (rec[mid] < target) {
                // 保证不会小于target
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }


    public static void main(String[] args) {
        // TreeMap<Integer, Integer> map = new TreeMap<>();
        // map.put(1,1);
        // map.put(2,1);
        // map.put(3,1);
        // System.out.println(map.ceilingKey(2));
        // System.out.println(map.floorKey(0));

        int[] ints = {1,4,4,4, 4, 6, 9};
        System.out.println(binarySearch(ints, 5));
    }
}